package com.xuyang.leetcode.offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Li Xuyang
 * @date 2020/4/7 17:47
 * 字符流中第一个不重复的字符
 */
public class FirstAppearingOnce54 {
    /*
    题目描述
    请实现一个函数用来找出字符流中第一个只出现一次的字符。
    例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
    当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
    输出描述:
    如果当前字符流没有存在出现一次的字符，返回#字符。
     */

    /*
        时间复杂度O(1)，空间复杂度O（1）：无须存储所有字符

        这道题目的大致思路其实都差不多，只不过看了许多答案，发现都是存储了所有字符，然后再进行遍历判断
        其实并不需要这样，这样子 HR 哪里会给 Offer 呢？ 用户 txlstars 的回答和本文的优化相同（绝对不是面向 Ctrl+C 编程的～）

        字符出现次数的判断（不重复字符）：
        这个做法大致相同，利用 Hash 思想采用128大小的计数数组进行计数也好，或者是使用 Map 键值对映射也好，都差不多，使用数组会更简单。

        字符出现顺序的判断（第一个字符）：
        这里就是改进的关键之处了，容易发现，字符流中不重复的字符可能同时存在多个，我们只要把这些 “不重复字符” 保存起来就可以，而无需保存那些重复出现的字符，而为了维护字符出现的顺序，我们使用队列（先进先出）这一结构，先出现的不重复字符先输出：

        入队：获取字符流中的一个字符时，当我们判断它是不重复时，将它加入队列；
        输出/出队：注意，因为队列中存储的 “不重复字符” 在一系列的流读取操作后，随时有可能改变状态（变重复），所以，队列中的字符不能直接输出，要先进行一次重复判断，如果发现队头字符已经重复了，就将它移出队列并判断新的队头，否则，输出队头的值；

        复杂度计算：
        从上面的描述来看，好像存在一个循环，队列的长度好像无边无际，就给人一种O(n)的感觉，其实，并不是，有如下结论：

        通过分析可以发现，循环（出队）的最大次数其实就是队列的长度，而队列的长度最大为128；
        并且随着时间的推移，队列长度 总体 先增大，后减小，正常条件下，最终队列会为空（因为随着字符流的增大，重复的字符会越来越多，队列就会不断地移除元素而越来越短）；
        更愉快的是，如果队列长度不减小，则循环就只执行一次，返回速度快，如果队列长度减小了，那么，循环次数上限也就减小了；
        所以时间、空间复杂度是一致的，都是常数级，可是这是为什么呢，分析如下：

        字符的重复判断，因为使用的是直接 Hash，而且功能是计数，没有冲突，所以是O(1)；
        只有不重复的字符才入队列，但是不重复的字符有几个呢？ASCII字符最多也就128个，那么同一字符会不会多次入队呢？ 不会的，见3；
        只有队头元素变得重复了才执行循环，所以执行循环就意味着队列长度要变小。要注意，根据题意，字符的出现次数只增不减！！！所以，出队的字符不会再入队，队列长度总体上只会越来越小（或者上升到峰值就不再上升了，128种字符用尽）。

     */

    int[] charCnt = new int[128];
    Queue<Character> queue = new LinkedList<>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        if (charCnt[ch]++ == 0) { //新来的单身字符，入队
            queue.add(ch);

        }
    }

    //return the first appearence once char in current stringstream
    public char firstAppearingOnce() {
        Character CHAR = null;
        char c = 0;
        while ((CHAR = queue.peek()) != null) {
            c = CHAR.charValue();
            if (charCnt[c] == 1) { //判断是否脱单了，没脱单则输出
                return c;
            } else {
                queue.remove();
            }
        }

        return '#';

    }
}
